package com.company.fiveeight;

import java.util.*;

public class Main2 {
    public static void main(String[] args) {
        int[] data = {1,7,2,6,-1,4,8};
        ArrayList<ArrayList<Integer>> arrayLists = binaryTreeScan(data);
        for (int i = 0; i < arrayLists.size(); i++) {
            ArrayList<Integer> da = arrayLists.get(i);
            System.out.println(Arrays.toString(da.toArray()));
        }
    }

    public static ArrayList<ArrayList<Integer>> binaryTreeScan (int[] input) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        int i = 0,len = input.length;
        TreeNode root = new TreeNode(input[i]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (i < len && !queue.isEmpty()){
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                TreeNode t = queue.poll();
                i++;
                if(i < len && input[i] != -1){
                    TreeNode sub = new TreeNode(input[i]);
                    t.left = sub;
                    queue.offer(sub);
                }
                i++;
                if(i < len && input[i] != -1){
                    TreeNode sub = new TreeNode(input[i]);
                    t.right = sub;
                    queue.offer(sub);
                }
            }
        }
        res.add(preOrder(root));
        res.add(inOrder(root));
        res.add(postOrder(root));

        return res;
    }

    private static ArrayList<Integer> preOrder(TreeNode root){
        ArrayList<Integer> res = new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        while (!s.isEmpty()){
            TreeNode t = s.pop();
            res.add(t.value);
            if(t.right != null){
                s.push(t.right);
            }
            if(t.left != null){
                s.push(t.left);
            }
        }
        return res;
    }

    private static ArrayList<Integer> inOrder(TreeNode root){
        ArrayList<Integer> res = new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        while (!s.isEmpty() || root != null){
            if(root != null){
                s.push(root);
                root = root.left;
            }else {
                root = s.pop();
                res.add(root.value);
                root = root.right;
            }
        }
        return res;
    }

    private static ArrayList<Integer> postOrder(TreeNode root){
        ArrayList<Integer> res = new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        while (!s.isEmpty()){
            TreeNode t = s.pop();
            res.add(0,t.value);
            if(t.left != null){
                s.push(t.left);
            }
            if(t.right != null){
                s.push(t.right);
            }
        }
        return res;
    }
}

class TreeNode{
    int value;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value){
        this.value = value;
    }
}
